// 《围棋》作者版权所有。保留所有权利。
// 此源代码的使用受BSD样式
// 许可证的约束，该许可证可以在许可证文件中找到。ABCFDG 

package par

import (
	"math/rand"
	"sync"
	"sync/atomic"
)

// 工作管理一组并行执行的工作项，每个项最多执行一次。
// 集合中的项目必须都是有效的映射键。
type Work struct {
	f       func(any) // 为每个项目运行的函数
	running int       // 跑步者总数

	mu      sync.Mutex
	added   map[any]bool // 添加到集合
	todo    []any        // 尚未运行的项目
	wait    sync.Cond    // 等待todo为空
	waiting int          // 等待todo的跑步者人数
}

func (w *Work) init() {
	if w.added == nil {
		w.added = make(map[any]bool)
	}
}

// 添加将项目添加到工作集（如果尚未添加）。
func (w *Work) Add(item any) {
	w.mu.Lock()
	w.init()
	if !w.added[item] {
		w.added[item] = true
		w.todo = append(w.todo, item)
		if w.waiting > 0 {
			w.wait.Signal()
		}
	}
	w.mu.Unlock()
}

// Do在工作集中的项上并行运行f，
// 一次最多运行n次f调用。
// 当添加到工作集中的所有内容都已处理完毕时返回。
// 在调用Do（或Do立即返回）之前，至少应该向工作集添加一个项
// 但允许f（项）向工作集添加新项。
// Do只能在给定的工作中使用一次。
func (w *Work) Do(n int, f func(item any)) {
	if n < 1 {
		panic("par.Work.Do: n < 1")
	}
	if w.running >= 1 {
		panic("par.Work.Do: already called Do")
	}

	w.running = n
	w.f = f
	w.wait.L = &w.mu

	for i := 0; i < n-1; i++ {
		go w.runner()
	}
	w.runner()
}

// 运行者在w中执行工作，直到两个都没有什么要做的
// 所有运行者都在等待工作。
// （然后所有参赛者返回。）
func (w *Work) runner() {
	for {
		// 等待做某事。全部完成。
		w.mu.Lock()
		for len(w.todo) == 0 {
			w.waiting++
			if w.waiting == w.running {
				w.wait.Broadcast()
				w.mu.Unlock()
				return
			}
			w.wait.Wait()
			w.waiting--
		}

		// 随机选择要做的事情，
		// 消除病理性争用
		// 以防几乎同时添加的项目
		// 最有可能发生争用。
		i := rand.Intn(len(w.todo))
		item := w.todo[i]
		w.todo[i] = w.todo[len(w.todo)-1]
		w.todo = w.todo[:len(w.todo)-1]
		w.mu.Unlock()

		w.f(item)
	}
}

// 缓存对每个键运行一次操作，并缓存结果。
type Cache struct {
	m sync.Map
}

type cacheEntry struct {
	done   uint32
	mu     sync.Mutex
	result any
}

// Do调用函数f的条件是且仅当Do是第一次使用此键调用时。
// 在对f的一个调用返回之前，对给定密钥的Do调用不会返回。
// Do返回对f的一次调用返回的值。
func (c *Cache) Do(key any, f func() any) any {
	entryIface, ok := c.m.Load(key)
	if !ok {
		entryIface, _ = c.m.LoadOrStore(key, new(cacheEntry))
	}
	e := entryIface.(*cacheEntry)
	if atomic.LoadUint32(&e.done) == 0 {
		e.mu.Lock()
		if atomic.LoadUint32(&e.done) == 0 {
			e.result = f()
			atomic.StoreUint32(&e.done, 1)
		}
		e.mu.Unlock()
	}
	return e.result
}

// Get返回与键关联的缓存结果。
// 如果没有这样的结果，则返回nil。
// 如果正在计算key的结果，Get不会等待计算完成。
func (c *Cache) Get(key any) any {
	entryIface, ok := c.m.Load(key)
	if !ok {
		return nil
	}
	e := entryIface.(*cacheEntry)
	if atomic.LoadUint32(&e.done) == 0 {
		return nil
	}
	return e.result
}

// 清除将删除缓存中的所有条目。
// 
// Get的并发调用可能会返回旧值。执行
// 的并发调用可能会返回旧值或将结果存储在已删除的条目中。
// 
// TODO（jayconrod）：删除内部/load中的包缓存清除功能
// 。
func (c *Cache) Clear() {
	c.m.Range(func(key, value any) bool {
		c.m.Delete(key)
		return true
	})
}

// Delete从映射中删除一个条目。对不存在的
// 条目调用Delete是安全的。Delete将快速返回，即使密钥的结果
// 仍在计算中；计算将完成，但无法通过缓存访问
// 结果。
// 
// TODO（jayconrod）：删除内部/load中的包缓存清除功能
// 。
func (c *Cache) Delete(key any) {
	c.m.Delete(key)
}

// DeleteIf为映射中的每个键调用pred。如果pred为密钥返回true，则
// DeleteIf将删除相应的条目。如果某个键的结果是
// 仍在计算中，则DeleteIf将删除该项，而无需等待
// 计算完成。无法通过缓存访问结果。
// 
// TODO（jayconrod）：删除内部/load中的包缓存清除功能
// 。
func (c *Cache) DeleteIf(pred func(key any) bool) {
	c.m.Range(func(key, _ any) bool {
		if pred(key) {
			c.Delete(key)
		}
		return true
	})
}
